package com.itheima.d03_sort_bubble;

import java.util.Arrays;

public class Test {


    public static void main(String[] args) {
        //优化：进一步优化外层循环比较的轮数
        //优化思想：
        int count = 0;

        int[] arr = {1,2,3,4,5,6};

        int n = arr.length-1; //每一轮比较的边界值

        for (int j = 0; j < arr.length-1; j++) {
            int last = 0; //记录最后一次交换数据位置
            //外层循环：控制比较的轮数
            System.out.println("外层循环，第："+(j+1)+"轮");
            for (int i = 0; i < n; i++) {
                count++;
                //内层循环：控制每轮比较的次数
                //核心思想：相邻数据两两比较，大的放到后面
                //相邻的两个数据：arr[i]   arr[i+1]
                System.out.println("\t\t内层循环，比较："+arr[i]+"和"+arr[i+1]+"，当前第"+(i+1)+"次");
                if(arr[i] > arr[i+1]){
                    swap(arr, i, i+1);
                    last = i;
                }
            }
            n = last;

            //优化：如果一次循环中没有发生数据交换，则说明数组已经有序了，可以提前结束循环
            if(n ==0 ){
                break;
            }
        }
        System.out.println("一共比较的次数："+count);
        System.out.println(Arrays.toString(arr));
    }

    private static void three() {
        //优化：进一步优化内层循环比较的次数
        //优化思想：记录最后一次交换数据的位置，此位置作为下一次交换的边界
        int count = 0;

        int[] arr = {10, 5, 20, 30, 40, 45};

        int n = arr.length-1; //每一轮比较的边界值

        for (int j = 0; j < arr.length-1; j++) {
            int last = 0; //记录最后一次交换数据位置
            //外层循环：控制比较的轮数
            System.out.println("外层循环，第："+(j+1)+"轮");
            for (int i = 0; i < n; i++) {
                count++;
                //内层循环：控制每轮比较的次数
                //核心思想：相邻数据两两比较，大的放到后面
                //相邻的两个数据：arr[i]   arr[i+1]
                System.out.println("\t\t内层循环，比较："+arr[i]+"和"+arr[i+1]+"，当前第"+(i+1)+"次");
                if(arr[i] > arr[i+1]){
                    swap(arr, i, i+1);
                    last = i;
                }
            }
            n = last;
        }
        System.out.println("一共比较的次数："+count);
        System.out.println(Arrays.toString(arr));
    }


    /*
        优化：内层循环每轮比较的次数
        优化思路：内层循环每轮比较的次数：减去当前轮次
     */
    private static void two() {
        int[] arr = {10, 5, 20, 30, 40, 15};

        for (int j = 0; j < arr.length-1; j++) {
            //外层循环：控制比较的轮数
            System.out.println("外层循环，第："+(j+1)+"轮");
            for (int i = 0; i < arr.length-1 -j ; i++) {
                //内层循环：控制每轮比较的次数
                //核心思想：相邻数据两两比较，大的放到后面
                //相邻的两个数据：arr[i]   arr[i+1]
                System.out.println("\t\t内层循环，比较："+arr[i]+"和"+arr[i+1]+"，当前第"+(i+1)+"次");
                if(arr[i] > arr[i+1]){
                    swap(arr, i, i+1);
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }


    private static void one() {
        int[] arr = {10, 5, 20, 30, 40, 15};

        for (int j = 0; j < arr.length-1; j++) {
            //外层循环：控制比较的轮数
            System.out.println("外层循环，第："+(j+1)+"轮");
            for (int i = 0; i < arr.length-1; i++) {
                //内层循环：控制每轮比较的次数
                //核心思想：相邻数据两两比较，大的放到后面
                //相邻的两个数据：arr[i]   arr[i+1]
                System.out.println("\t\t内层循环，比较："+arr[i]+"和"+arr[i+1]+"，当前第"+(i+1)+"次");
                if(arr[i] > arr[i+1]){
                    swap(arr, i, i+1);
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }


    //交换
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
